"""
#### 此函数已被弃用：已修改的v2性能和v3持平，不需要v3了 ####
quicksort_v3
改进：和pivot值相等的元素有一半的概率交换，用一个布尔变量决定是否交换，每次交换时该变量值将反转
"""
import random


def rand_partition_v3(sequence, p, r):
    i = random.randint(p, r)
    sequence[r], sequence[i] = sequence[i], sequence[r]

    equal_replace = True

    def replace():
        nonlocal equal_replace
        equal_replace = not equal_replace
        return equal_replace

    x = sequence[r]
    i = p
    for j in range(p, r):
        # if sequence[j] == x:
        #     equal_replace = not equal_replace
        if sequence[j] < x or sequence[j] == x and replace():
            sequence[i], sequence[j] = sequence[j], sequence[i]
            i += 1

    sequence[i], sequence[r] = sequence[r], sequence[i]
    return i


def _quicksort_v3(sequence, p, r):
    if p < r:
        q = rand_partition_v3(sequence, p, r)
        _quicksort_v3(sequence, p, q - 1)
        _quicksort_v3(sequence, q + 1, r)


def quicksort_v3(sequence):
    _quicksort_v3(sequence, 0, len(sequence) - 1)


# if __name__ == '__main__':
    # print(replace())
    # print(replace())
    # print(replace())
    # print(replace())
